// Copyright (c) 2009-2010, Jeremy Brewer
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// * Redistributions of source code must retain the above copyright notice,
// this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

package galaxie500.numeric;

import galaxie500.exceptions.ValueError;

/**
 * Simple polynomial class
 * 
 * Class for representing a polynomial function.
 * 
 * @author Jeremy Brewer
 */
public class Polynomial implements Function {
  private double[] coefficients;

  /**
   * Constructs a polynomial from the array of coefficients, with the first
   * value giving the 0th order (constant) term.
   * 
   * @param coefficients The array of coefficients. This array is copied by
   *        reference.
   * @throws ValueError If any of the coefficients is NaN or infinite
   */
  public Polynomial(double[] coefficients) {
    assert coefficients != null;
    this.coefficients = coefficients;
    for (int i = 0; i < coefficients.length; i++) {
      double c = coefficients[i];
      if (Double.isNaN(c) || Double.isInfinite(c)) {
        throw new ValueError("coefficient " + i + " is bad: " + c);
      }
    }
  }

  /**
   * @return The order of the polynomial
   */
  public int order() {
    return coefficients.length - 1;
  }

  /**
   * @return The internal array of coefficients. Useful in tests or when making
   *         a copy of a polynomial without allocating new memory.
   */
  public double[] coefficients() {
    return coefficients;
  }

  /**
   * Returns the value of the polynomial at x. The polynomial is evaluated using
   * Horner's rule so that N - 1 multiplications and N additions are used for a
   * polynomial of order N.
   * 
   * @param x The location to evaluate at
   */
  public double valueAt(double x) {
    double y = coefficients[coefficients.length - 1];
    for (int i = coefficients.length - 2; i >= 0; i--) {
      y = x * y + coefficients[i];
    }
    return y;
  }

  /**
   * @return The derivative of this polynomial.
   */
  public Polynomial derivative() {
    if (coefficients.length <= 1) {
      return new Polynomial(new double[] {0.0});
    }
    double[] c = new double[coefficients.length - 1];
    for (int i = 0; i < c.length; i++) {
      c[i] = (double) (i + 1) * coefficients[i + 1];
    }
    return new Polynomial(c);
  }

  /**
   * @return Returns the indefinite integral of the polynomial. By convention,
   *         the undetermined constant is chosen to be 0.
   */
  public Polynomial indefiniteIntegral() {
    double[] c = new double[coefficients.length + 1];
    c[0] = 0.0; // Arbitrary, so we choose 0.
    for (int i = 0; i < coefficients.length; i++) {
      c[i + 1] = coefficients[i] / (double) (i + 1);
    }
    return new Polynomial(c);
  }

  /**
   * Returns the integral of this polynomial from [a, b].
   * 
   * @param a The starting point of integration
   * @param b The end point of integration
   * @return The integral from a to b.
   */
  public double integrate(double a, double b) {
    Polynomial p = indefiniteIntegral();
    return p.valueAt(b) - p.valueAt(a);
  }

  /**
   * @return A string representation of a polynomial.
   */
  @Override
  public String toString() {
    StringBuilder b = new StringBuilder();
    b.append(coefficients[0]);    
    for (int i = 1; i < coefficients.length; i++) {
      b.append(" + " + coefficients[i] + " x");
      if (i != 1) b.append("^" + i);
    }
    return b.toString();
  }
}
